package com.lft.tree08.binary_sort_tree;

/**
 * 二分搜索树
 */
public class BSTDemo {
	public static void main(String[] args) {
		BST bst = new BST();
		bst.add(3);
		bst.add(5);
		bst.add(4);
		bst.add(1);
		bst.add(2);
		bst.add(7);
		bst.add(8);
		System.out.println("中序遍历");
		bst.infixOrderTraverse();
		
		System.out.println("是否包含值为 5 的节点：" + bst.contains(5));
		System.out.println("最大值：" + bst.max());
		System.out.println("最小值：" + bst.min());
		bst.removeElement(5);
		
		System.out.println("中序遍历");
		bst.infixOrderTraverse();
		
		bst.removeElement(5);
		System.out.println("中序遍历");
		bst.infixOrderTraverse();
		
	}
}

/**
 * 数据是可比较的，需要实现Comparable接口
 * @param <E>
 */
class BST<E extends Comparable<E>> {
	private Node root;
	private int size;
	
	public BST() {
		root = null;
		size = 0;
	}
	
	// /**
	//  * 添加节点——第一版本
	//  * @param e
	//  */
	// public void add(E e) {
	// 	if (root == null) {
	// 		root = new Node(e);
	// 		size++;
	// 	}
	// 	add(root, e);
	// }
	//
	// /**
	//  * 递归实现添加节点——第一版本
	//  * @param node 根节点
	//  * @param e    待添加的值
	//  */
	// private void add(Node node, E e) {
	// 	// 待添加的节点等于根节点，不做处理
	// 	if (node.e.equals(e)) {
	// 		return;
	// 	}
	// 	// 待添加节点大于根节点，并且右子树为空，插入到右子节点位置。
	// 	else if (e.compareTo(node.e) > 0 && node.rightChild == null) {
	// 		node.rightChild = new Node(e);
	// 		size++;
	// 		return;
	// 	}
	// 	// 待添加节点小于根节点，并且左子树为空，插入到左子节点位置。
	// 	else if (e.compareTo(node.e) < 0 && node.leftChild == null) {
	// 		node.leftChild = new Node(e);
	// 		size++;
	// 		return;
	// 	}
	// 	// 待添加节点大于根节点，在右子树中寻找插入位置。
	// 	if (e.compareTo(node.e) > 0) {
	// 		add(node.rightChild, e);
	// 	}
	// 	// 待添加节点小于根节点，在左子树中寻找插入位置。
	// 	else {
	// 		add(node.leftChild, e);
	// 	}
	// }
	
	/**
	 * 添加节点——第二版本
	 * @param e
	 */
	public void add(E e) {
		root = add(root, e);
	}
	
	/**
	 * 修改add方法,使其有返回值,返回插入新节点后二分搜索树的根
	 * @param node
	 * @param e
	 * @return
	 */
	private Node add(Node node, E e) {
		if (node == null) {
			size++;
			return new Node(e);
		}
		if (e.compareTo(node.e) > 0) {
			node.rightChild = add(node.rightChild, e);
		} else if (e.compareTo(node.e) < 0) {
			node.leftChild = add(node.leftChild, e);
		}
		return node;
	}
	
	/**
	 * 判断是否包含指定元素的节点
	 * @param e
	 * @return
	 */
	public boolean contains(E e) {
		return contains(root, e);
	}
	
	private boolean contains(Node node, E e) {
		if (node == null) {
			return false;
		}
		if (node.e.equals(e)) {
			return true;
		} else if (e.compareTo(node.e) > 0) {
			return contains(node.leftChild, e);
		} else {
			return contains(node.rightChild, e);
		}
	}
	
	/**
	 * 中序遍历
	 */
	public void infixOrderTraverse() {
		infixOrderTraverse(root);
	}
	
	private void infixOrderTraverse(Node node) {
		if (node == null) {
			System.out.println("节点为空，无法遍历");
			return;
		}
		if (node.leftChild != null) {
			infixOrderTraverse(node.leftChild);
		}
		System.out.println(node);
		if (node.rightChild != null) {
			infixOrderTraverse(node.rightChild);
		}
	}
	
	/**
	 * 找到最小值
	 * @return
	 */
	public E min() {
		return minNode(root).e;
	}
	
	/**
	 * 二叉搜索树的最小值就是一直找左子节点。
	 * @param node
	 * @return
	 */
	private Node minNode(Node node) {
		if (node == null) {
			return null;
		}
		if (node.leftChild == null) {
			return node;
		}
		return minNode(node.leftChild);
	}
	
	/**
	 * 找到最大值
	 * @return
	 */
	public E max() {
		return maxNode(root).e;
	}
	
	/**
	 * 二叉搜索树的最大值就是一直找右子节点。
	 * @param node
	 * @return
	 */
	private Node maxNode(Node node) {
		if (node == null) {
			return null;
		}
		if (node.rightChild == null) {
			return node;
		}
		return maxNode(node.rightChild);
	}
	
	/**
	 * 删除最小值结点
	 * @return
	 */
	public E removeMin() {
		// 保存最小值，用于返回
		E result = min();
		root = removeMin(root);
		return result;
	}
	
	/**
	 * 删除以node为根结点的最小值结点，并且返回新的根结点
	 * @param node
	 * @return
	 */
	private Node removeMin(Node node) {
		if (node == null) {
			return null;
		}
		if (node.leftChild == null) {
			// 当前结点删除后需要将它的右孩子给父亲结点作为左孩子
			Node right = node.rightChild;
			node.rightChild = null;
			size--;
			
			return right;
		}
		node.leftChild = removeMin(node.leftChild);
		return node;
	}
	
	/**
	 * 删除最大值
	 * @return
	 */
	public E removeMax() {
		E result = max();
		root = removeMax(root);
		return result;
	}
	
	/**
	 * 删除以node为根结点的最大值结点，并且返回新的根结点
	 * @param node
	 * @return
	 */
	private Node removeMax(Node node) {
		if (node == null) {
			return null;
		}
		if (node.rightChild == null) {
			// 当前结点删除后需要将它的左孩子给父亲结点作为右孩子
			Node left = node.leftChild;
			node.leftChild = null;
			size--;
			return left;
		}
		node.rightChild = removeMax(node.rightChild);
		return node;
	}
	
	/**
	 * 删除指定节点
	 * @param key
	 */
	public void removeElement(E key) {
		root = removeElement(root, key);
	}
	
	private Node removeElement(Node node, E key) {
		if (node == null) {
			return null;
		}
		// 要删除的值大于当前节点值。向右递归查找删除。
		if (key.compareTo(node.e) > 0) {
			node.rightChild = removeElement(node.rightChild, key);
			return node;
		}
		// 要删除的值小于当前节点值。向左递归查找删除。
		else if (key.compareTo(node.e) < 0) {
			node.leftChild = removeElement(node.leftChild, key);
			return node;
		}
		// 要删除的值，跟当前节点的值相等。处理删除。
		else {
			// 左子树为空，右子树不为空。
			if (node.leftChild == null && node.rightChild != null) {
				Node right = node.rightChild;
				node.rightChild = null;
				size--;
				return right;
			}
			// 右子树为空，左子树不为空。
			if (node.rightChild == null && node.leftChild != null) {
				Node left = node.leftChild;
				node.leftChild = null;
				size--;
				return left;
			}
			// 待删除的节点左右子树均不为空
			// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
			Node minNode = minNode(node.rightChild);
			// 用这个节点顶替待删除节点的位置
			minNode.rightChild = removeMin(node.rightChild);
			minNode.leftChild = node.leftChild;
			node.rightChild = node.leftChild = null;
			size--;
			return minNode;
		}
	}
	
	/**
	 * 判断这个节点是否是二叉排序树
	 * @return
	 */
	public boolean isBST() {
		return isBST(root);
	}
	
	/**
	 * 如果一个二叉树是一个二叉排序树，则反回 true.
	 * @param node
	 * @return
	 */
	private boolean isBST(Node node) {
		if (node == null) {
			return true;
		}
		// 左子树最小值大于根节点，不符合BST原则
		if (node.leftChild != null && minNode(node.leftChild).e.compareTo(node.e) > 0) {
			return false;
		}
		// 右子树最大值小于根节点，不符合BST原则
		if (node.rightChild != null && maxNode(node.rightChild).e.compareTo(node.e) < 0) {
			return false;
		}
		// 左子树或右子树不是BST，整体不是BST
		if (!isBST(node.leftChild) || !isBST(node.rightChild)) {
			return false;
		}
		return true;
	}
	
	/**
	 * 判断两棵树是否相同。
	 * @param another
	 * @return
	 */
	public boolean isSameTree(BST another) {
		return isSameTree(root, another.root);
	}
	
	private boolean isSameTree(Node node, Node another) {
		// 两个都为空，返回 true
		if (root == null && another == null) {
			return true;
		}
		// 两个都不为空，递归比较
		else if (root != null && another != null) {
			// 比较当前节点的值是否相等。
			return root.e.equals(another.e)
					// 递归比较左子树
					&& isSameTree(root.leftChild, another.leftChild)
					// 递归比较右子树
					&& isSameTree(root.rightChild, another.rightChild);
		} else {
			// 一个空，一个不为空。返回false
			return false;
		}
	}
	
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		generateBSTString(root, 0, res);
		return res.toString();
	}
	
	private void generateBSTString(Node node, int depth, StringBuilder res) {
		if (node == null) {
			res.append(generateDepthString(depth) + "null\n");
			return;
		}
		res.append(generateDepthString(depth) + node.e + "\n");
		generateBSTString(node.leftChild, depth + 1, res);
		generateBSTString(node.rightChild, depth + 1, res);
	}
	
	private String generateDepthString(int depth) {
		StringBuilder res = new StringBuilder();
		for (int i = 0; i < depth; i++) {
			res.append("--");
		}
		return res.toString();
	}
	
	/**
	 * 获取二叉搜索树节点数
	 * @return
	 */
	public int size() {
		return this.size;
	}
	
	public Node getRoot() {
		return root;
	}
	
	/**
	 * 判断二叉树是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return root == null;
	}
	
	/**
	 * 内部节点类
	 */
	public class Node {
		/**
		 * 数据域
		 */
		public E e;
		/**
		 * 左子节点
		 */
		public Node leftChild;
		/**
		 * 右子节点
		 */
		public Node rightChild;
		
		public Node(E e) {
			this.e = e;
			this.leftChild = null;
			this.rightChild = null;
		}
		
		@Override
		public String toString() {
			return "Node{" +
					"e=" + e +
					'}';
		}
	}
}

